/**
 * KMP算法
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{
    int len;
    char *ch;
} String;

/**
 * 获取next数组，这个很重要
 * 先找最长相同前后缀，在赋值给next数组，这个next数组里面的具体求法“记住就好了”
 * 做题的时候，可以直接看，找共同前后缀
 * 
 * @param t 目标数组（短的那个）
 * @param next next数组，0号元素为0，而不是视频中的-1
 */
void get_next(String t, int next[])
{
    int i = 1;
    int j = 0;
    next[0] = 0;
    while (i < t.len)//用双指针，往中间查找也是可以的，但是这里显然不是两边到中间
    {
        if (j == 0 && t.ch[i] != t.ch[j])
            next[i++] = 0;
        else if (t.ch[i] != t.ch[j])
            j = next[j - 1];
        else if (t.ch[i] == t.ch[j])
            next[i++] = ++j;
    }
}

/**
 * kmp实现
 * @param t 长字符串
 * @param p 短字符串
 * @param pos 开始下标
 * @return int  第一个正确匹配子串的开始下标
 */
int kmp(String t, String p, int pos)
{
    int i = pos;
    int j = 0;
    // 初始化next数组
    int *next = (int *)malloc(sizeof(int) * p.len);
    get_next(p, next);
    // i是长字符串下标，j是短字符串下标
    while (i < t.len && j < p.len)
    {
        if (j == 0 && t.ch[i] != p.ch[j])
        { // p的第一个字符都不匹配，直接从下一个开始，j还是=0
            i++;
        }
        else if (t.ch[i] == p.ch[j])
        {
            i++;
            j++;
        }
        else if (t.ch[i] != p.ch[j])
        {
            j = next[j - 1];
        }
    }
    if (j > p.len - 1)
    { // 返回数组下标
        return i - p.len;
    }
    return -1; // 失败返回-1
}

int main(void)
{
    String s, t;
    char a[9] = "abcaby";
    char b[20] = "abxabcabcaby";
    t.len = strlen(b);
    t.ch = b;
    s.len = strlen(a);
    s.ch = a;
    printf("%d ", kmp(t, s, 0)); // 从0开始查找，给出匹配的下标
    //返回6，也就是abcaby
}